package hot100.普通数组;

/**
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * 子数组是数组中的一个连续部分。
 *
 * @ https://leetcode.cn/problems/maximum-subarray/description/?envType=study-plan-v2&envId=top-100-liked
 * @date 2025/08/25
 */
public class 最大子数组和_53 {

    public static void main(String[] args) {

    }

    /**
     * 前缀和+哈希表
     * 记录之前最小的前缀和，当前前缀和 - 之前最小的前缀和 = 已当前数字结尾的最大和数组
     */
    public int maxSubArray(int[] nums) {

        int maxSub = Integer.MIN_VALUE;
        int curSum = 0, preMinSum = 0;
        for (int num : nums) {
            curSum += num;

            maxSub = Math.max(maxSub, curSum - preMinSum);

            preMinSum = Math.min(preMinSum, curSum);
        }
        return maxSub;

    }

}
